package leet27removeelement

// 思路：
// 1. 双指针法，快慢指针
// 2. 快指针遍历数组，慢指针记录不等于val的元素位置
// 3. 遇到不等于val的元素，将其放在慢指针的位置，并将慢指针向后移动一位
// 4. 遍历结束后，慢指针的位置即为新数组的长度
// 5. 返回慢指针的位置
// 6. 时间复杂度O(n)，空间复杂度O(1)
// 7. 注意：题目要求原地修改数组，所以不能使用额外的空间
// 8. 注意：题目要求返回新数组的长度，所以不能直接返回慢指针的位置
func RemoveElement(nums []int, val int) int {
	// 快指针
	fast := 0
	// 慢指针
	slow := 0
	// 遍历数组
	for fast < len(nums) {
		// 如果快指针指向的元素不等于val
		if nums[fast] != val {
			// 将快指针指向的元素放在慢指针的位置
			nums[slow] = nums[fast]
			// 慢指针向后移动一位
			slow++
		}
		// 快指针向后移动一位
		fast++
	}
	return slow
}

// 换一个思路:
// 双指针法，左右指针
// 1. 左指针从头开始，右指针从尾开始
// 2. 左指针指向的元素等于val，右指针指向的元素不等于val
// 3. 交换左右指针指向的元素
// 4. 左指针向后移动一位，右指针向前移动一位
// 5. 直到左右指针相遇
// 6. 返回左指针的位置
// 7. 时间复杂度O(n)，空间复杂度O(1)
func RemoveElement2(nums []int, val int) int {
	// 左指针
	left := 0
	// 右指针
	right := len(nums) - 1
	// 遍历数组
	for left <= right {
		// 如果左指针指向的元素等于val，右指针指向的元素不等于val
		if nums[left] == val && nums[right] != val {
			// 交换左右指针指向的元素
			nums[left], nums[right] = nums[right], nums[left]
		}
		// 左指针向后移动一位
		if nums[left] != val {
			left++
		}
		// 右指针向前移动一位
		if nums[right] == val {
			right--
		}
	}
	return left
}

// 参考：https://leetcode.cn/problems/remove-element/solution/zheng-li-shu-zu-by-leetcode-solution-2j8g/
